﻿#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
#include"head.h"
void test1()
{
	int a[] = { 1,2,4,8,9,12,3,5,10 };
	Heap hp;
	HeapInit(&hp);
	for (int i = 0; i <sizeof(a)/sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	HeapDestory(&hp);
}
void HeapSort(int* a, int n)
{
	////向上调整建堆(O(n*logn)
	//for (int i = 1; i < n; i++)
	//{
	//	Adjustup(a,i);
	//}
	//向下调整建堆(O(N))
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(a, n, i);
	}

	//排升序   向下调整堆(n*logn)
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		Adjustdown(a, end, 0);//（注意传参）
		end--;
	}
	

}

//void CreateNDate()
//{
//	// 造数据
//	int n = 10000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//
//	for (size_t i = 0; i < n; ++i)
//	{
//		int x = rand() % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//
//	fclose(fin);
//}

//void PrintTopK(const char* filename, int k)
//{
//	// 1. 建堆--用a中前k个元素建堆
//	//打开文件
//	FILE* fout = fopen(filename, "r");
//	if (fout == NULL)
//	{
//		perror("fopen fail");
//		exit(-1);
//	}
//	int* heap = (int*)malloc(sizeof(int) * k);
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(fout, "%d", &heap[i]);
//	}
//	//向下调整建堆
//	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//	{
//		Adjustdown(heap, k, i);
//	}
//	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
//	int x = 0;
//	while (fscanf(fout, "%d", &x) != EOF)
//	{
//		if (x > heap[0])
//		{
//			heap[0] = x;
//			Adjustdown(heap, k, 0);
//		}
//	}
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", heap[i]);
//	}
//	printf("\n");
//	fclose(fout);
//}
//
//



int main()
{
	//test1();
	int a[] = { 3,9,6,5,4 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	//CreateNDate();
	/*PrintTopK("data.txt",5);*/
	return 0;
}
